4483. Козленок, который учился считать

 

Козлёнок работает контролёром на пароме. Его задача – следить за тем, чтобы паром не затонул из-за превышения грузоподъёмности. Сегодня на пароме осталось всего два свободных билета, а также возможность принять дополнительно ещё k килограммов.

В этом лесу есть единственная длинная дорога, вдоль которой живут звери. Помогите козлёнку определить, сможет ли он на заданном участке леса найти двух пассажиров.

 

Вход.  В первой строке заданы два числа n (2 ≤ n ≤ 106) и k (1 ≤ k ≤ 109) – количество зверей в лесу и оставшаяся грузоподъёмность парома соответственно.

Во второй строке содержится n чисел – массы каждого из зверей.

Затем задано число m (1 ≤ m ≤ 105) – количество запросов.

В следующих m строках содержится по три числа t, l, r:

·        Если t = 1, то 1 ≤ l < r ≤ n – проверить, можно ли выбрать двух пассажиров среди зверей на отрезке [l; r].

·        Если t = 2, то 1 ≤ l ≤ n, 1 ≤ r ≤ 109 – изменить массу зверя с номером l на r килограммов.

 

Выход. Для каждого запроса типа 1 выведите “Yes”, если козлёнок сможет найти двух пассажиров на указанном отрезке, и “No”, если не сможет.

Запрос типа 2 означает, что масса зверя с номером l изменилась и теперь равна r килограммам.

 

Пример входа

Пример выхода

6 9

1 3 1 6 6 7

8

1 1 6

1 1 2

2 4 7

1 4 5

1 5 6

2 1 7

2 3 8

1 1 6

Yes

Yes

No

No

Yes

 

 

РЕШЕНИЕ

структуры данных - дерево отрезков, единичная модификация

 

Анализ алгоритма

Можно построить дерево отрезков, поддерживающее два минимума. Однако нас в задаче интересуют не сами минимумы на отрезках, а лишь факт существования двух чисел, сумма которых не превышает k.

В листья дерева отрезков занесем веса пассажиров. В остальных вершинах будем хранить значения согласно следующих правил:

·        если сумма минимальных значений в левом и правом поддеревьях не превышает k, то на интервале [l; r] существуют два подходящих пассажира. В этом случае в вершину, соответствующую интервалу [l; r], заносим 0.

·        В противном случае в вершину записываем минимум из значений её сыновей.

 

Рассмотрим выполнение запросов.

·        если минимум на отрезке [l; r] равен 0, то существуют два пассажира с подходящей суммой, ответ “Yes”.

·        В противном случае ответ “No”.

 

Пример

Построим дерево отрезков для k = 9 и весов пассажиров 7, 3, 8, 7, 6, 7.

Из фундаментальных отрезков только вершина [1; 6] будет содержать 0.

 

Реализация алгоритма

Объявим массив SegTree для хранения дерева отрезков. Массы зверей храним в массиве a.

 

#define MAX 1000010

#define MAX_INT 1050000000

int SegTree[4*MAX];

int a[MAX];

 

Функция f выполняет слияние значений сыновей в вершинах дерева отрезков. Дерево отрезков поддерживает операцию нахождения минимума. Однако если сумма значений в левом и правом сыне не превышает k, возвращаем 0.

Кроме того, если хотя бы один из сыновей уже содержит 0, это означает, что на его отрезке существуют два подходящих пассажира, поэтому также возвращаем 0.

 

int f(int a, int b)

{

  if (a == 0 || b == 0 || a + b <= k) return 0;

  return min(a,b);

}

 

Функция BuildTree строит дерево отрезков. На вход она принимает номер текущей вершины v и границы отрезка lpos и rpos, соответствующие вершине v. При слиянии сыновей используется функция f.

 

void BuildTree(int v, int lpos, int rpos)

{

  if (lpos == rpos)

    SegTree[v] = a[lpos];

  else

  {

    int mid = (lpos + rpos) / 2;

    BuildTree(2 * v, lpos, mid);

    BuildTree(2 * v + 1, mid + 1, rpos);

    SegTree[v] = f(SegTree[2 * v], SegTree[2 * v + 1]);

  }

}

 

Функция Query выполняет запрос на отрезке [left; right]. Вершине v соответствует отрезок [lpos, rpos].

·        Если на отрезке [left, right] существуют два пассажира, сумма масс которых не превышает k, функция Query возвращает 0.

·        В противном случае она возвращает минимальный вес пассажира на данном отрезке.

 

int Query(int v, int lpos, int rpos, int left, int right)

{

  if (left > right) return MAX_INT;

  if ((lpos == left) && (rpos == right)) return SegTree[v];

  int mid = (lpos + rpos) / 2;

  return f(Query(2 * v, lpos, mid, left, min(right, mid)),

          Query(2 * v + 1, mid + 1, rpos, max(left, mid + 1), right));

}

 

Функция Update обновляет значение элемента с индексом pos, присваивая ему val. Вершине v соответствует отрезок [lpos, rpos].

 

void Update(int v, int lpos, int rpos, int pos, int val)

{

  if (lpos == rpos)

    SegTree[v] = val;

  else

  {

    int mid = (lpos + rpos) / 2;

    if (pos <= mid) Update(2 * v, lpos, mid, pos, val);

    else Update(2 * v + 1, mid + 1, rpos, pos, val);

    SegTree[v] = f(SegTree[2 * v], SegTree[2 * v + 1]);

  }

}

 

Основная часть программы. Читаем массы зверей в массив a, начиная с нулевого индекса.

 

scanf("%d %d",&n,&k);

for (i = 0; i < n; i++) scanf("%d",&a[i]);

 

Строим дерево отрезков по элементам массива a[0..n – 1].

 

BuildTree(1,0,n-1);

 

Последовательно обрабатываем запросы.

 

scanf("%d",&q);

for (j = 0; j < q; j++)

{

  scanf("%d %d %d",&t,&l,&r);

  if (t == 1)

  {

    int Res = Query(1,0,n-1,l-1,r-1);

    if (Res == 0) printf("Yes\n"); else printf("No\n");

  }

  else

    Update(1,0,n-1,l-1,r) ;

}